"""
1、如何判断链表是否有环？如何找出环的入口节点？
    在 Python 面试中，链表的基础题型几乎每次都出现。
    今天我们就来剖析一道经典题目：如何判断一个链表是否有环？
    如果你掌握了这一技巧，那下一步你应该深入学习：如何找到环的入口节点？

问题描述：给定一个单向链表的头节点 head，判断链表中是否存在环，如果存在，请返回环的起始节点。

"""

"""
解法一：判断链表是否有环（快慢指针）
首先我们使用**快慢指针（Floyd 判圈算法）**来判断链表是否有环：
    • slow 每次走一步
    • fast 每次走两步
    • 如果两者在某个节点相遇，就说明存在环
"""


# def has_cycle(head: ListNode) -> bool:
#     slow = fast = head
#     while fast and fast.next:
#         slow = slow.next
#         fast = fast.next.next
#         if slow == fast:
#             return True
#     return False


"""
解法二：找出环的入口（重点）
    当快慢指针相遇之后，说明链表中存在环。此时我们可以使用如下方法找出环的起点（入口）：
    
    步骤解析：
    1. 让其中一个指针（如 slow）回到链表头 head；
    2. 然后两个指针都改为每次走一步；
    3. 当两个指针再次相遇时，就是环的入口。
    
    原理解释：
    设：
    • a 是头节点到环入口的长度；
    • b 是环入口到相遇点的长度；
    • c 是环剩下的长度（使得一圈为 b + c）；
    
    因为快指针走的距离是慢指针的两倍：
    2(a + b) = a + b + n(b + c)
    推导得：a = c + (n - 1)(b + c)
    
    说明从头节点走 a 步、从相遇点走 c 步，两者会在环的入口节点重合。
"""


class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None


def detect_cycle(head: ListNode) -> ListNode:
    """
    检测链表中的环，返回环的起始节点。如果无环返回 None。
    """
    slow = fast = head

    # 第一步：判断是否有环
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # 无环

    # 第二步：找环的入口
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # 即为环的起始节点